package main.剑指OfferⅠ;

import java.util.*;

public class Day6 {
    public static void main(String[] args) {
        System.out.println("剑指Offer32-Ⅰ.从上到下打印二叉树");
        System.out.println("剑指Offer32-Ⅱ.从上到下打印二叉树Ⅱ");
        System.out.println("剑指Offer32-Ⅲ.从上到下打印二叉树Ⅲ");
    }
}

//class TreeNode {
//    int val;
//    TreeNode left;
//    TreeNode right;
//    TreeNode(int x) { val = x; }
//}
class Offer32_Ⅰ{
    public int[] levelOrder(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        int[] result;
        if (root!=null){
            Queue<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                root=queue.poll();
                list.add(root.val);
                if (root.left!=null) queue.add(root.left);
                if (root.right!=null) queue.add(root.right);
            }
        }
        result = new int[list.size()];
        for (int i=0;i<list.size();i++){
            result[i]=list.get(i);
        }
        return result;
    }
}

class Offer32_Ⅱ{
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        int curLevel=0,nextLevel=0;
        if (root!=null){
            Queue<TreeNode> queue=new LinkedList<>();
            curLevel=1;
            queue.add(root);
            List<Integer> curList=new ArrayList<>();
            while (!queue.isEmpty()){
                if (curLevel!=0) curLevel--;
                else {//结算本层节点
                    list.add(curList);
                    curLevel=nextLevel-1;
                    curList=new ArrayList<>();
                    nextLevel=0;
                }
                root=queue.poll();
                curList.add(root.val);
                if (root.left!=null){
                    nextLevel++;
                    queue.add(root.left);
                }
                if (root.right!=null){
                    nextLevel++;
                    queue.add(root.right);
                }
            }
            list.add(curList);
        }
        return list;
    }
}

class Offer32_Ⅲ{
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<>();
        int curLevel=0,nextLevel=0;
        if (root!=null){
            Queue<TreeNode> queue=new LinkedList<>();
            curLevel=1;
            queue.add(root);
            List<Integer> curList=new ArrayList<>();
            boolean flag=false;
            while (!queue.isEmpty()){
                if (curLevel!=0) curLevel--;
                else {//结算本层节点
                    if (flag) Collections.reverse(curList);
                    flag=!flag;
                    list.add(curList);
                    curLevel=nextLevel-1;
                    curList=new ArrayList<>();
                    nextLevel=0;
                }
                root=queue.poll();
                curList.add(root.val);
                if (root.left!=null){
                    nextLevel++;
                    queue.add(root.left);
                }
                if (root.right!=null){
                    nextLevel++;
                    queue.add(root.right);
                }
            }
            if (flag) Collections.reverse(curList);
            list.add(curList);
        }
        return list;
    }
}